package com.algorithm.leveltraverse;

import java.util.LinkedList;
import java.util.Queue;

public class LevelTraverse {
    public static void main(String[] args) {
        Node root = createTree();
        Queue<Node> queue = new LinkedList<Node>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            System.out.println(node.getKey());
            if (node.getLeft() != null) {
                queue.offer(node.getLeft());
            }
            if (node.getRight() != null) {
                queue.offer(node.getRight());
            }
        }
    }

    public static Node createTree() {
        Node root = new Node(3, null, null);
        int[] arr = {4,2,1,6,8,7,9,5};
        for (int i = 0; i < arr.length; i++) {
            insert(root, arr[i]);
        }
        return root;
    }

    public static void insert(Node root, int key) {
        Node node = new Node(key, null, null);
        Node p = root;
        while (p != null) {
            if (p.getKey() > key) {
                if (p.getLeft() == null) {
                    p.setLeft(node);
                    break;
                } else {
                    p = p.getLeft();
                }
            } else {
                if (p.getRight() == null) {
                    p.setRight(node);
                    break;
                } else {
                    p = p.getRight();
                }
           }
        }
    }
    public static void preOrder(Node root) {
        System.out.println(root.getKey());
        if (root.getLeft() != null) {
            preOrder(root.getLeft());
        }
        if (root.getRight() != null) {
            preOrder(root.getRight());
        }
    }
}
